package com.github.algorithm.sort;


import com.sun.org.apache.xpath.internal.operations.Mod;

import javax.management.modelmbean.ModelMBean;

/**
 * @author Stephen
 * @date 2020/6/8 13:30
 */
public class MergeSort {

    public void mergeSort(int[] array) {
        int left = 0;
        int right = array.length-1;
        int[] temp = new int[array.length];
        mergeSort(array, temp, left, right);
    }

    public void mergeSort(int[] array, int[] temp, int left, int right) {
        int middle;
        if (right - left + 1 > 28) {
            middle = (left + right) / 2;
            mergeSort(array, temp, left, middle);
            mergeSort(array, temp, middle+1, right);
            modMerge(array, temp, left, right, middle);
        }
    }

    public void modMerge(int[] array, int[] temp, int left, int right, int middle) {
        int i, j, k, leftIndex, rightIndex;
        //copy left sub array
        for (i=left; i<=middle; i++)
            temp[i] = array[i];
        //copy right sub array in inverse order
        for (j=1; j<=right-middle; j++)
            temp[right-j+1] = array[j+middle];
        //merge the smaller element into the array
        for (leftIndex=left, rightIndex=right, k=left; k<=right; k++)
            if (temp[leftIndex] <= temp[rightIndex])
                array[k] = temp[leftIndex++];
            else array[k] = temp[rightIndex--];
    }
}
